package com.zhongge.sort;

/**
 * @ClassName SortUtil
 * @Description TODO 排序类
 * @Author 笨忠
 * @Date 2025/7/31 21:22
 * @Version 1.0
 */
public class SortUtil {
    /**
     * 插入排序：直接插入排序
     * @param arr 待排序的数组
     */
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (arr[j] > tmp) {
                    arr[j + 1] = arr[j];
                } else {
                    arr[j + 1] = tmp;
                    break;
                }
            }
            //跳出循环的时候：会出现 j = -1的情况 即 j<0的情况
            //eg: 3 2 1
            //    j i
            if (j < 0) {
                arr[j + 1] = tmp;
            }
        }
    }

    /**
     * 插入排序：希尔排序
     * @param arr
     */
    public static void shellInsert(int[] arr) {
        int gap = arr.length;
        while (gap > 1) {
            gap /= 2;
            shell(arr, gap);
        }
    }

    private static void shell(int[] arr, int gap) {
        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i - gap;
            for (; j >= 0; j-=gap) {
                if (arr[j] > tmp) {
                    arr[j + gap] = arr[j];
                } else {
                    arr[j + gap] = tmp;
                    break;
                }
            }
            //跳出循环的时候：会出现 j = -1的情况 即 j<0的情况
            //eg: 3 2 1
            //    j i
            if (j < 0) {
                arr[j + gap] = tmp;
            }
        }
    }
}
